/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/k-sum
   @Language: C++
   @Datetime: 16-02-09 09:03
   */


// Method 1, Time O(n*k*t), Space O(n*k*t), Time 201ms
class Solution {
public:
	/**
	 * @param A: An integer array
	 * @param k: A positive integer (k <= length(A))
	 * @param target: An integer
	 * @return: An integera
	 */
	int kSum(vector<int> &A, int k, int target) {
		// write your code here
		vector<vector<vector<int> > > dp(A.size()+1,vector<vector<int> >(k+1,vector<int>(target+1,0)));
		for(int i=1; i<=A.size(); ++i){
			if (A[i-1]<=target)
				for(int j=i; j<=A.size(); dp[j++][1][A[i-1]]=1);
		}
		for(int i=1; i<=A.size(); ++i){
			for(int j=2; j<=min(i,k); ++j){
				for(int t=1; t<=target; ++t){
					dp[i][j][t]=dp[i-1][j][t];
					if(t-A[i-1]>0) dp[i][j][t]+=dp[i-1][j-1][t-A[i-1]];
				}
			}
		}
		return dp[A.size()][k][target];
	}
};


// Method 2, Time O(n*k*t), Space O(k*t), Time 151ms
class Solution {
public:
	/**
	 * @param A: An integer array
	 * @param k: A positive integer (k <= length(A))
	 * @param target: An integer
	 * @return: An integera
	 */
	int kSum(vector<int> &A, int k, int target) {
		// write your code here
		vector<vector<int> > dp(k+1,vector<int>(target+1,0));
		dp[0][0]=1;
		for(int i=0; i<A.size(); ++i)
			for(int j=k; j; --j)
				for(int t=target; t>=A[i]; --t)
					dp[j][t] += dp[j-1][t-A[i]];
		return dp[k][target];
	}
};
